import java.util.*;

public class Leetcode {
}

//leetcode:1218:最长定差子序列
class Solution1 {
    public int longestSubsequence(int[] arr, int difference) {
        //利用哈希表进行快速查找优化
        Map<Integer,Integer> hash = new HashMap<>();
        int ret = 1;
        for(int x : arr){
            hash.put(x,hash.getOrDefault(x-difference,0)+1);
            ret = Math.max(ret,hash.get(x));
        }
        return ret;
    }
}

//leetcode:873:最长的斐波那契子序列的长度
class Solution2 {
    public int lenLongestFibSubseq(int[] arr) {
        //利用哈希表存入数据进行查找时间的优化
        Map<Integer,Integer> hash = new HashMap<>();
        int n = arr.length;
        for(int i = 0; i < n; i++){
            hash.put(arr[i],i);
        }

        //初始化，将数组中的位置值初始化为2，因为我们是要确定最后两位置的值，看是否能找到这两个值的前一个值，因此我们可以确定此时的长度一定是为2的
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }

        int ret = 2;
        for(int j = 2; j < n; j++){//固定最后一个数
            for(int i = 1; i < j; i++){//枚举倒数第二个数
                //确定第一个数的值
                int a = arr[j] - arr[i];
                //判断这个值是否是比第二个数小，并且在哈希表中存在
                if(a < arr[i] && hash.containsKey(a)){
                    //如果存在就代表此时的值可以和这两个数组成一个斐波那契数列，所有让长度加1
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                //得到最大值
                ret = Math.max(ret,dp[i][j]);
            }
        }
        //如果ret的长度是小于3的，就代表不是斐波那契数列就返回0
        return ret < 3 ? 0 : ret;
    }
}